package hot100;


/*
 * Author：江松
 * Date：2023/4/13 10:48
 *
 戳气球：
 1,记忆化搜索——自顶向下
 因为戳气球会导致数组不断变化，反过来想，在确定边界的情况下放入气球
 因此i>=j-1说明区间中没气球，作为递归边界，然后枚举区间中的每个球k
 因为会重复计算，所以做成记忆化
 注意：val边界是0-n+1且初始化为1，因为要把所有气球都装进来

 2，动态规划——自底向上（区间DP）
 */

public class Main312 {
    public int maxCoins(int[] nums) {
        int n=nums.length;
        int f[][]=new int[n+2][n+2];
        int val[]=new int[n+2];
        for(int i=0;i<n;++i)val[i+1]=nums[i];
        val[0]=val[n+1]=1;
        //根据状态转移方程，j这种再后面的要先被计算出来，因此要逆序遍历
        for(int i=n+1;i>=0;--i){
            for(int j=i+1;j<=n+1;++j){
                for(int k=i+1;k<j;++k){
                    f[i][j]=Math.max(f[i][k]+f[k][j]+val[i]*val[j]*val[k],f[i][j]);
                }
            }
        }
        return f[0][n+1];
    }
    /*
    int f[][];
    public int solve(int []val,int i,int j){
        if(i>=j-1){
            return 0;
        }
        if(f[i][j]!=0)return f[i][j];
        int res=0;
        //枚举每个球
        for(int k=i+1;k<j;++k){
            res=Math.max(val[i]*val[j]*val[k]+solve(val,i,k)+solve(val,k,j),res);
        }
        return f[i][j]=res;
    }

    public int maxCoins(int[] nums) {
        int n=nums.length;
        f=new int[n+2][n+2];
        int val[]=new int[n+2];
        for(int i=0;i<n;++i){
            val[i+1]=nums[i];
        }
        val[0]=val[n+1]=1;
        return solve(val,0,n+1);
    }
*/
}
